#include<stdio.h>
#include<stdlib.h>
#include<stack>
using namespace std;
typedef struct node
{
	int data;
	struct node *left,*right;
}*tree;
tree newNode(int data){
    tree node=(tree)malloc(sizeof(struct node));
    node->data=data;
    node->left=NULL;
    node->right=NULL;
    return node;
}
tree create_bst(tree root,int data){
    if(root==NULL)
        return newNode(data);
    if(root->data>data)
        root->left=create_bst(root->left,data);
    else
        root->right=create_bst(root->right,data);
    return root;
}
int tag=0;
void GetPath(tree root,tree p,tree stack[],int *top)
{
	if(root!=NULL&&tag==0)//未找到P且根结点不为空时进入循环
	{
		stack[++(*top)]=root;
		if(root->data==p->data)
		{
			tag=1;
			return;
		}
		else
		{
			GetPath(root->left,p,stack,top);
			GetPath(root->right,p,stack,top);
			if(tag==0)//左右子树均未找到，则元素出栈。
				free(stack[(*top)--]);
		}
	}
}
void preOrder(tree root){
    if(root==NULL)
        return;
    printf("%d ",root->data);
    preOrder(root->right);
    preOrder(root->left);
}
bool path(tree root,tree p,stack<tree> &s){
    tree curNode=root,pre=NULL;
    if(root==NULL||p==NULL||!s.empty())
        return false;
    while(curNode||!s.empty()){
        while(curNode){//深度优先
            s.push(curNode);
            if(curNode==p)
                return true;
            curNode=curNode->left;
        }
        if(!s.empty()){//curNode节点的左子树为空还是没找到，继续往右子树找
            curNode=s.top();
            while(curNode->right==NULL||pre!=NULL&&curNode->right==pre){
                //curNode的右孩子为空，其右孩子已经访问过
                pre=s.top();
                s.pop();
                curNode=s.top();
            }
            curNode=curNode->right;//继续往非空且未访问的右子树走一步
        }
    }
    return false;
}
void pathtoStack(tree root,tree p,stack<tree> &s){
    if(root==NULL||p==NULL||!s.empty()){
        return;
    }
    tree curNode=root,pre=NULL;
    while(curNode||!s.empty()){
        while(curNode){
            s.push(curNode);
            if(curNode==p)
                return;
            curNode=curNode->left;
        }//左子树为空还是没找到
        if(!s.empty()){
            curNode=s.top();
            while(curNode->right==NULL||curNode->right==pre){
                //curNode的右孩子为空，其右孩子已经访问过
                pre=s.top();
                s.pop();
                curNode=s.top();
            }
            curNode=curNode->right;
        }
    }
}
int main(){
    int a[10]={10,2,3,49,8,20,78,21,8,11};
    /*
           10
        /     \ 
      2        49
       \       / \
        3     20  78
        \    / \
         8  11 21
         \
          8
    */
    tree root=NULL;
    for(int i=0;i<10;i++)
        root=create_bst(root,a[i]);
    preOrder(root);
    stack<tree> s;
    pathtoStack(root,root->right->left->right,s);
    printf("\n------\n");
    while(!s.empty()){
        printf("%d ",s.top()->data);
        s.pop();
    }
    return 0;
}